package top.minuy.structure.graph.route.hamilton;

import top.minuy.structure.graph.cc.bfs.CC;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 哈密尔顿路径
 * 数量参考 Leet Code 980
 *
 * @author Minuy
 * @time 10:11
 * @date 2021/11/23
 */
public class HamiltonPath {

    Graph g;
    boolean[] isVisited;
    int[] pre;

    int s, t;
    boolean hasPath;

    public HamiltonPath(Graph g, int s, int t) {
        this.g = g;
        this.s = s;
        this.t = t;

        isVisited = new boolean[g.V()];
        pre = new int[g.V()];


        // 加上联通分量的判断会提升效率
        // 因为这个算法的时间复杂度非常高 : O(n!)
        CC cc = new CC(g);
        if (cc.isConnected(s,t)) {
            hasPath = dfs(s, s, g.V());
        }
        // 如果不联通则不存在路径
        // hasPath = dfs(s, s, g.V());
    }

    private boolean dfs(int v, int parent, int left) {

        isVisited[v] = true;
        pre[v] = parent;
        left--;

        if (left == 0 && v == t) {
            return true;
        }

        for (int w : g.adj(v)) {
            if (!isVisited[w]) {
                if (dfs(w, v, left)) {
                    return true;
                }
            }
        }

        isVisited[v] = false;
        return false;
    }

    public Iterable<Integer> path() {
        ArrayList<Integer> ret = new ArrayList<>();
        if (!hasPath) {
            return ret;
        }

        int cur = t;
        while (cur != s) {
            ret.add(cur);
            cur = pre[cur];
        }
        ret.add(s);

        Collections.reverse(ret);
        return ret;
    }


    @Override
    public String toString() {
        return path().toString();
    }
}
